Data compression is a branch of information theory in which the primary objective is to minimize the amount of data to be transmitted. As applied to rigid magnetic disks, the aim of data compression is to reduce redundancy in the stored or communicated data, thus increasing the effective data density on the storage medium. Ultimately, this means that more information can be stored using data compression algorithms than could be stored if compression techniques were unavailable. In this manner, compressing data to be stored or transmitted reduces storage and/or communication costs.
Because data compression involves transforming a string of characters in some representation (such as ASCII (American Standard Code for Information Interchange) code into a new string (e.g., of bits) that contains the same information but whose length is as small as possible, various problems arise. The most important of these is related to the fact that it is virtually impossible to predict a priori the size of a compressed data record. In other words, when a data compression algorithm operates on a string of data having a length of N-bytes, there is no way of deducing ahead of time what the size of the compressed data record will be. All that is known is that the compressed data string will be (CR*N) bytes long, where CR is the compression ratio (usually &lt;1, however, in some instances the compression ratio may be &gt;1 so that the compressed data requires more storage than the uncompressed data). Thus, the unpredictable nature of the compression/decompression process creates certain difficulties in storing large volumes of compressed data efficiently on a hard disk drive. This is especially the case when the disk has been preformatted with a fixed-length sector size. In prior approaches using a preformatted rigid-disk having fixed-length sector sizes (e.g., 512 bytes), there is usually a one-to-one correspondence between the number of bytes of a logical block and a physical sector on the disk. Storing compressed data for a 512-byte logical block in a 512-byte physical block would result in large portions of unused memory on the disk.
A computer hard disk is basically a three or four dimensional object. The track, or cylinder comprises the radial dimension of the disk, the number of heads (i.e., the sides of the disks) represents the vertical dimension; and the number of sectors within a track is the third, circular dimension. How much data can be stored inside each sector (i.e., the size of each sector) is the fourth dimension. Most often, a hard disk is physically formatted such that the available storage area is divided into a plurality of equal-sized regions. By way of example, most hard disks are divided into a fixed set of 512-byte sectors. Logical formatting, on the other hand, is essentially the adoption of a disk to the standards of the operating system. From a logical standpoint, the operating system treats the hard disk as a one-dimensional object and the sectors of the disk as a sequential list of logical block addresses. The logical formatting therefore is the road map that the operating system uses to read/write data information from/to the disk.
When compressed data is written to a hard disk, the smallest logical block size available for storing that information is dependent upon the physical formatting of the disk. In most instances, this means that the compressed data is stored into 512-byte large logical blocks. But since the compressed data is normally much smaller than a 512-byte block, this conventional method of storing compressed data results in inefficient use of disk space. Basically, relatively large portions of the hard disk go unused and are unavailable for further information storage. By way of example, for a compression ratio of 2:1, a 512-byte data string is compressed to a 256-byte string. When stored in the standard 512-byte logical block on a preformatted hard disk, the result is 256-bytes of wasted memory space.
What is needed then is a way of storing compressed data information onto a formatted hard disk more efficiently. As will be seen, the present invention provides a method of structuring the storage of compressed data on a hard disk in an embedded controller environment. The present invention is beneficial for increasing the storage capacity of a disk drive by utilizing the efficiency of compressed data, adding flexibility, and for enhancing the operating performance of the disk drive system. Moreover, the present invention allows management of the data compression/decompression to be performed transparent to the host processor such that no change need be made to the host operating system hardware or software.